// There is an ant which can walk around on a planar grid. The ant can move
// one space at a time left, right, up or down. That is, from (x, y) the
// ant can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where
// the sum of the digits of the x coordinate plus the sum of the digits of
// the y coordinate are greater than 25 are inaccessible to the ant. For
// example, the point (59, 79) is inaccessible because 5 + 9 + 7 + 9 = 30,
// which is greater than 25. How many points can the ant access if it
// starts at (1000, 1000), including (1000, 1000) itself?

#include <iostream>
#include <set>
#include <vector>
#include <assert.h>
#include <set>
#include <queue>
#include <iterator>

using namespace std;

const int MAX = 699; // 6 + 9 + 9 = 24
const int CAP = 23;

int cost( int i ) {
    int result = 0;
    while ( i ) {
	result += i % 10;
	i /= 10;
    }
    return result;
}

class Space {
    int x_,y_;
  public:
    Space( int x, int y )
	    : x_( x ),
	      y_( y ) {
    }
    int x() const { return x_; }
    int y() const { return y_; }
    int cost() const { return ::cost( x_ ) + ::cost( y_ ); }

    // valid moves from this space/point (left,right,up,down)
    set< Space > moves() const {
	// return vector instead of set?
	set< Space > result;
	if ( x_ < MAX ) result.insert( Space( x_+1, y_ ) );
	if ( x_ > 0 ) result.insert( Space( x_-1, y_ ) );
	if ( y_ < MAX ) result.insert( Space( x_, y_+1 ) );
	if ( y_ > 0 ) result.insert( Space( x_, y_-1 ) );
	return result;
    }
};

bool operator<( Space const &a, Space const &b ) {
    return a.y() < b.y() || ( a.y() == b.y() &&  a.x() < b.x() );
}

ostream &operator<<( ostream &o, Space const &s ) {
    return o << s.x() << "," << s.y();
}


class BitMap {
  public:
    BitMap( unsigned size ) :
	    map_( size+1 ) {
	for ( unsigned i = 0; i < map_.size(); i++ ) {
	    map_[i].resize( size+1 );
	}
    }

    void set( const Space &s ) {
	assert( !get( s ) );
	map_[ s.x() ][ s.y() ] = true;
    }
    
    bool get( const Space &s ) const {
	return map_[ s.x() ][ s.y() ];
    }
    
  private:
    vector< vector<bool> > map_;
};

int main ( int argc, char *argv[] ) {

    BitMap visited( MAX );
    BitMap scored( MAX ); // for verification

    // BFS: size of q should not be *too* large (est. 700+700)
    queue< Space > q;
    q.push( Space( 0, 0 ) );

    int score = 0;
    while ( q.size() ) {
	Space cur = q.front(); q.pop();
	if ( visited.get( cur ) ) continue;
	visited.set( cur );
	if ( cur.cost() <= CAP ) {
	    scored.set( cur );
	    score++;
	    set< Space > moves = cur.moves();
	    for ( set< Space >::iterator it = moves.begin();
		  moves.end() != it; it++ ) {
		if ( !visited.get( *it ) ) { // check of debatable value
		    q.push( *it );
		}
	    }
	}
    }
    
    cout << "Score : " << score << endl;

    //                     - verification -
    // cout << "------------------" << endl;

    for ( int i = 0; i <= MAX; i++ ) {
	for ( int j = 0; j <= MAX; j++ ) {
	    Space s( i, j );
	    if ( scored.get( s ) ) {
		assert( s.cost() <= 23 );
		// cout << 'O';
	    } else if ( s.cost() > 23 ) {
		// cout << 'X';
	    } else {
		// cout << ' ';
	    }
	}
	// cout << endl;
    }
}
